/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Mar 27, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;

import org.junit.Test;

/**
 * @version 1.0
 * @description Two elements of a binary search tree (BST) are swapped by
 *              mistake.
 * 
 *              Recover the tree without changing its structure.
 * 
 *              Note: A solution using O(n) space is pretty straight forward.
 *              Could you devise a constant space solution? confused what
 *              "{1,#,2,3}" means?
 * 
 *              OJ's Binary Tree Serialization: The serialization of a binary
 *              tree follows a level order traversal, where '#' signifies a path
 *              terminator where no node exists below.
 * 
 *              Here's an example: 
 *              	 1 
 *                  / \ 
 *                 2   3 
 *                    / 
 *                   4 
 *                    \ 
 *                     5 
 *              The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
 */
public class RecoverBinarySearchTree {

	class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	// just two element are wrong, so just change the two element
	public void recoverTree1(TreeNode root) {
		if (root == null)
			return;
		ArrayList<TreeNode> inorder = new ArrayList<TreeNode>();
		// 中序遍历存储输出结果
		inOrderList(root, inorder);
		
		int first = -1, second = -1;
		for (int i = 0; i < inorder.size() - 1; i++) {
			if (inorder.get(i).val > inorder.get(i + 1).val && first < 0)
				first = i;
			if (inorder.get(i).val > inorder.get(i + 1).val && first >= 0)
				second = i + 1;
		}
		int temp = inorder.get(first).val;
		inorder.get(first).val = inorder.get(second).val;
		inorder.get(second).val = temp;
	}
	
	private void inOrderList(TreeNode root, ArrayList<TreeNode> res) {
		if (root == null)
			return;
		
		inOrderList(root.left, res);
		res.add(root);
		inOrderList(root.right, res);
	}
	
	@Test
	public void test() {
		TreeNode root = new TreeNode(4);
		root.left = new TreeNode(5);
		root.right = new TreeNode(6);
		root.left.left = new TreeNode(1);
		root.left.right = new TreeNode(3);
		root.right.left = new TreeNode(2);
		root.right.right = new TreeNode(7);
		
		recoverTree1(root);
	}
}
